package de.uniLuebeck.tcs.algorithmics;

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class Sudoku extends BacktrackingSkeletton<SudokuInstance, SudokuInstance>{

	@Override
	protected SudokuInstance readNewInstance(BufferedReader reader) throws IOException {
		
		int[][] intArray = null;
		String aktuelleZeile;
		String[] horizontaleZeilenArray, vertikaleZeilenArray;
		int groesseSudoku = 0;
		
		while( null != (aktuelleZeile = reader.readLine())) {
			if (!aktuelleZeile.startsWith(">") && !aktuelleZeile.isEmpty() && aktuelleZeile.length() < 3){

				try{
					groesseSudoku = Integer.parseInt(aktuelleZeile);
				}
				catch(NumberFormatException ex2){
					throw ex2;
				}
				
				intArray = new int[groesseSudoku][groesseSudoku];
				
				vertikaleZeilenArray = reader.readLine().trim().split(" ");
				int j = 0;
				
				while (vertikaleZeilenArray.length > j && !vertikaleZeilenArray[0].equalsIgnoreCase(">")){
				
					for (int i=0;i<groesseSudoku;i++){
						
						try{
						intArray[j][i] = Integer.parseInt(vertikaleZeilenArray[i]);
						}
						catch(NumberFormatException ex){
							intArray[j][i] = 0;
						}
					}
					if (vertikaleZeilenArray.length > groesseSudoku){
						horizontaleZeilenArray = new String[vertikaleZeilenArray.length-groesseSudoku];
						for (int i=0;i<vertikaleZeilenArray.length-groesseSudoku;i++){
							horizontaleZeilenArray[i] = vertikaleZeilenArray[groesseSudoku+i];
						}
						vertikaleZeilenArray = horizontaleZeilenArray;
						
					}
					else if (null != (aktuelleZeile = reader.readLine())) {
						vertikaleZeilenArray = aktuelleZeile.trim().split(" ");
					}
						
					j++;
				}
			}
		}
		return new SudokuInstance(intArray);
	}

	@Override
	protected Iterator<SudokuInstance> computeExtensions(int l, List<SudokuInstance> x,
			SudokuInstance instance) {
		
		
		List<SudokuInstance>	extensions = new ArrayList<SudokuInstance>();
		
		SudokuInstance	lastExtension = new SudokuInstance(instance);
		if(0 != x.size()) {
			lastExtension = x.get(x.size() - 1);
		}
		
		System.out.println("Current solutions has " + lastExtension.getNumberOfOpenFields() + " of " + lastExtension.getNumberOfFields() + " open fields.");
		
		int f = lastExtension.getNextEmpty();
		if(0 < f) {
			int[]	values = lastExtension.getNumberPossibleValues();
			for(int i = 0; i < values.length; i++) {
				SudokuInstance	newInstance = new SudokuInstance(lastExtension);
				newInstance.setField(f, values[i]);
				
				extensions.add(newInstance);
			}
		}
		
		return	extensions.iterator();

//		List<int[][]>	result = new ArrayList<int[][]>();
//		
//		int numRows = instance.length;
//		int numCols = instance[0].length;
//		
//		int currentRow = l / numCols;
//		int currentCol = l % numCols;
//		
//		int[][] sudoku = x.get(x.size() - 1);
//		
//		if(0 == sudoku[currentRow][currentCol]) {
//			for(int i=0; i < numRows; i++) {
//				int[][] tmp = sudoku.clone();
//				tmp[currentRow][currentCol] = i + 1;
//				result.add(tmp);
//			}
//		} else {
//			result.add(sudoku.clone());
//		}
//		
//		return result.iterator();
	}

	@Override
	protected double getValue(int l, List<SudokuInstance> x, SudokuInstance instance) {
		int sudoku_groesse = x.get(x.size()-1).getNumberOfRows();
		double value = 0;
		for(int i = 0; i < sudoku_groesse; i++){
			for(int j = 0; j < sudoku_groesse; j++){
				int wert = x.get(x.size()-1).getField(i, j);
				if(wert != 0){
					value++;
				}
			}
		}
		return value;
	}

	@Override
	protected boolean isFeasibleSolution(int l, List<SudokuInstance> x,
			SudokuInstance instance) {
		if(0 == x.size()) {
			return	false;
		}
		
		int sudoku_groesse = x.get(x.size()-1).getNumberOfRows();
		int[] block = new int[sudoku_groesse];
		int[] block_kopie = new int[sudoku_groesse];
		
		//Zeilen ueberpruefen
		for(int i = 0; i < sudoku_groesse; i++){
			for(int j = 0; j < sudoku_groesse; j++){
				int feld_wert = x.get(x.size()-1).getField(i, j);
				block[j] = feld_wert;
				block_kopie = block.clone();
			}
			for( int u = 0; u < block.length; u++ ){
				for( int v = 0; v < block_kopie.length; v++ ){
					if(block[u] != 0 && block[u] == block_kopie[v] && u!=v ){
						return false;
					}
				}
			}
		}
		//Spalten ueberpruefen
		for(int i = 0; i < sudoku_groesse; i++){
			for(int j = 0; j < sudoku_groesse; j++){
				int feld_wert = x.get(x.size()-1).getField(j, i);
				block[j] = feld_wert;
				block_kopie = block.clone();
			}
			for( int u = 0; u < block.length; u++ ){
				for( int v = 0; v < block_kopie.length; v++ ){
					if(block[u] != 0 && block[u] == block_kopie[v] && u!=v ){
						return false;
					}
				}
			}
		}
		//Bloecke ueberpruefen
		int block_groesse = (int)java.lang.Math.sqrt(sudoku_groesse);
		for(int i = 0; i < block_groesse; i++){
			for(int j = 0; j < block_groesse; j++){
				int feld_wert = x.get(x.size()-1).getField(j, i);
				block[j] = feld_wert;
				block_kopie = block.clone();
			}
		}
		for( int u = 0; u < block.length; u++ ){
			for( int v = 0; v < block_kopie.length; v++ ){
				if(block[u] != 0 && block[u] == block_kopie[v] && u!=v ){
					return false;
				}
			}
		}
		return true;
	}

	@Override
	public void printSolution(Writer output, SudokuInstance instance)
	throws IOException {
		output.write("The optimal solution:\n\n");
		int sudoku_groesse = instance.getNumberOfRows();
		for(int i = 0; i < sudoku_groesse; i++){
			for(int j = 0; j < sudoku_groesse; j++){
				int feld_wert = instance.getField(i, j);
				output.write(feld_wert + " ");
			}
			output.write("\n");
		}
	}
}
